#include <iostream>

using namespace std;

template <class T>
class node
{
public:
    node() : pre(nullptr), next(nullptr) {}

public:
    node<T> *pre;
    node<T> *next;
    T data;
};

template <class T>
class list
{
public:
    // 默认构造
    list();
    // 带参数的构造函数
    list(unsigned int n, T data);
    // 复制构造
    list(list<T> &p);
    // 析构函数
    ~list();
    // 返回元素个数
    unsigned int getSize() { return size; }
    // 返回第一个元素节点
    node<T> *begin() { return ls->next; }
    // 返回最后一个元素节点
    node<T> *end() { return ls; }
    // 判断是否为空
    bool empty() { return ls->pre == ls->next; }
    // 插入元素
    void insert(node<T> *n, T data);
    // 删除元素
    node<T> *erase(node<T> *n);
    // 查找元素
    node<T> *find(T data);
    // 尾部插入元素
    void push_back(T data) { insert(ls, data); }
    // 头部插入元素
    void push_front(T data) { insert(ls->next, data); }
    // 销毁列表
    void destroy();
    // 清空元素
    void clear() { destroy(); }
    // 输出列表
    void print();
    // 返回第一个节点值
    T &front() { return ls->next->data; }
    // 返回最后一个节点值
    T &back() { return ls.pre.data; }

protected:
    node<T> *ls;
    unsigned int size;
};

template <class T>
list<T>::list() : size(0)
{
    ls = new node<T>();
    ls->pre = ls;
    ls->next = ls;
}

template <class T>
void list<T>::insert(node<T> *n, T data)
{
    node<T> *tmp = new node<T>();
    tmp->data = data;
    tmp->next = n;
    tmp->pre = n->pre;
    n->pre->next = tmp;
    n->pre = tmp;
    size++;
}

template <class T>
list<T>::list(unsigned int n, T data) : size(0)
{
    ls = new list<T>();
    ls->pre = ls;
    ls->next = ls;
    for (auto i = 0; i < n; i++)
        insert(ls, data);
}

template <class T>
node<T> *list<T>::erase(node<T> *n)
{
    node<T> *tmp = n->next;
    n->pre->next = n->next;
    n->next->pre = n->pre;
    delete n;
    size--;
    return tmp;
}

template <class T>
list<T>::list(list<T> &p) : size(p.getSize())
{
    ls = new list<T>();
    ls->pre = ls;
    ls->next = ls;
    node<T> *tmp = p.ls->next;
    while (tmp != p.ls)
    {
        insert(ls, tmp->data);
        tmp = tmp->next;
    }
}

template <class T>
void list<T>::destroy()
{
    node<T> *tmp = ls->next;
    while (tmp != ls)
        tmp = erase(tmp);
}

template <class T>
list<T>::~list()
{
    destroy();
    delete ls;
}

template <class T>
node<T> *list<T>::find(T data)
{
    node<T> *tmp = ls->next;
    while (tmp != ls)
    {
        if (tmp->data == data)
            return tmp;
        tmp = tmp->next;
    }
    return tmp;
}

template <class T>
void list<T>::print()
{
    node<T> *tmp = ls->next;
    cout << "size of list is:" << size << endl;
    while (tmp != ls)
    {
        cout << tmp->data << " ";
        tmp = tmp->next;
    }
    cout << endl;
}

int main()
{
    list<int> arr;
    arr.push_back(1);
    arr.push_back(2);
    arr.push_back(3);
    arr.push_back(4);
    cout << "输入4个元素后输出:" << endl;
    arr.print();
    cout << "查找元素并删除后输出:" << endl;
    auto tmp = arr.find(2);
    if (tmp != arr.end())
        arr.erase(tmp);
    arr.print();
    cout << "清空元素后输出:" << endl;
    arr.destroy();
    arr.print();
    cout << "判断元素是否为空:" << endl;
    cout << arr.empty() << endl;
    return 0;
}